﻿/* We are given a matrix of strings of size N x M. Sequences in the matrix we define as sets of several neighbor elements 
 * located on the same line, column or diagonal. Write a program that finds the longest sequence of equal strings in 
 * the matrix. Example:
 * 
 * ha fifi ho hi            s qq s
 * fo ha   hi xx            pp pp s
 * xxx ho ha  xx            pp qq s
 * ^ha, ha, ha              ^s, s, s
 */
using System;

class MaxSequence
{
    static void Main()
    {
        //get matrix size from user input
        uint N, M;

        //check for invalid input
        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error: invalid input! Please enter a positive integer. \r\n\t* Valid input: N > 0");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);

        iProvided = false; //reset iProvided
        do
        {
            if (iProvided == true) Console.WriteLine("Error: invalid input! Please enter a positive integer. \r\n\t* Valid input: M > 0");
            else iProvided = true;
            Console.Write("Enter M: ");
        } while (UInt32.TryParse(Console.ReadLine(), out M) == false || M < 1);

        Console.WriteLine("{0}x{1}", N, M);

        string[,] matrix = new string[N, M];
        for (int rowInput = 0; rowInput < N; rowInput++)
        {
            for (int colInput = 0; colInput < M; colInput++)
            {
                Console.Write("Enter element on row {0}, col {1}: ", rowInput+1, colInput+1);
                matrix[rowInput, colInput] = Console.ReadLine();
            }
        }

        //test cases
        //string[,] matrix = {
        //                      {"ha", "fifi", "ho", "hi"},
        //                      {"fo", "ha", "hi", "xx"},
        //                      {"xxx", "ho", "ha", "xx" }
        //                   };
        //string[,] matrix = {
        //                      {"s", "qq", "s"},
        //                      {"pp", "pp", "s"},
        //                      {"pp", "qq", "s" }
        //                   };

        PrintMatrix(matrix);

        /* we will split the program into several subtasks -   find the longest horizontal sequence of a row, 
         *                                               find the longest vertical sequence of a column,
         *                                               find the longest diagonal sequence, find the longest reverse diagonal
         *                                               sequence */
        
        int count = 0, maxCount = 0, arr_I = 0, col = 0;
        string element = null, maxElement = null, position = null;

        //horizontally
        for (int row = 0; row < N; row++)
        {
            string[] arrTmp = new string[M];
            for (col = 0, arr_I = 0; col < M; col++)
            {
                arrTmp[arr_I++] = matrix[row, col];
            }
 
            count = 0;
            element = "";
            count = GetMaxSequence(arrTmp, ref element);
 
            if (count == -1) continue;
 
            if (count > maxCount)
            {
                maxCount = count;
                maxElement = element;
                position = "horizontally";
            }
        }

        //vertically
        int rowV = 0;
        for (col = 0; col < N; col++)
        {
            string[] arrTmp = new string[N];
            for (rowV = 0, arr_I = 0; rowV < N; rowV++)
            {
                arrTmp[arr_I++] = matrix[rowV, col];
            }

            count = 0;
            element = "";

            count = GetMaxSequence(arrTmp, ref element);

            if (count == -1) continue;

            if (count > maxCount)
            {
                maxCount = count;
                maxElement = element;
                position = "vertically";
            }
        }

        //left to right diagonal
        int rt = (int)N - 1, ct = 0;
        for (col = 0; col < M; col++)
        {
            while (true)
            {
                if (rt > 0) rt--;
                if (rt == 0)
                    ct = col;
                else
                    ct = 0;
                string[] arrTmp = new string[N];
                arr_I = 0;

                for (int row = rt; row < N; row++, ct++)
                {
                    if (ct == M) break;
                    arrTmp[arr_I++] = matrix[row, ct];
                }

                count = 0;
                element = "";

                count = GetMaxSequence(arrTmp, ref element);

                if (count == -1) continue;

                if (count > maxCount)
                {
                    maxCount = count;
                    maxElement = element;
                    position = "diagonally";
                }
                if (rt == 0) break;
            }
        }

        //right to left diagonal
        rt = (int)N - 1;
        ct = 0;
        for (col = (int)M - 1; col >= 0; col--)
        {
            while (true)
            {
                if (rt > 0) rt--;
                if (rt == 0)
                    ct = col;
                else
                    ct = (int)M - 1;
                string[] arrTmp = new string[N];
                arr_I = 0;

                for (int row = rt; row < N; row++, ct--)
                {
                    if (ct == -1) break;
                    arrTmp[arr_I++] = matrix[row, ct];
                }

                count = 0;
                element = "";

                count = GetMaxSequence(arrTmp, ref element);

                if (count == -1) continue;

                if (count > maxCount)
                {
                    maxCount = count;
                    maxElement = element;
                    position = "diagonally";
                }
                if (rt == 0) break;
            }
        }

        if (maxCount > 0 && maxElement != "")
            Console.WriteLine("Found {0} occurrances of {1} {2}", maxCount, maxElement, position);
        else
            Console.WriteLine("Not found repeating elements!");
    }

    private static int GetMaxSequence(string[] array, ref string maxElement)
    {
        if (array.Length < 1) return -1;

        int count = 1, maxCount = 0;
        string element = "";

        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] == null) continue;

            if (element == array[i]) count++;

            if (element != array[i] || i == array.Length - 1)
            {
                if (count > maxCount)
                {
                    if (element == "") element = array[i];
                    maxElement = element;
                    maxCount = count;
                }
                element = array[i];
                count = 1;
            }
        }

        if (maxCount == 1 && maxElement != "")
        {
            maxCount = 0;
            maxElement = "";
        }

        return maxCount;
    }


    private static void PrintMatrix(string[,] matrix, int StartRow, int StartCol, int EndRow, int EndCol)
    {
        for (int row = StartRow; row < EndRow; row++)
        {

            for (int col = StartCol; col < EndCol; col++) Console.Write("{0,-5}", matrix[row, col]);
            Console.WriteLine();
        }
        Console.WriteLine();
    }


    private static void PrintMatrix(string[,] matrix, int startRow = 0, int startCol = 0)
    {
        for (int row = 0; row < matrix.GetLength(0); row++)
        {

            for (int col = 0; col < matrix.GetLength(1); col++) Console.Write("{0,-5}", matrix[row, col]);
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}

